package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
 * Difficulty : Easy
 *
 * 买卖股票
 * 给一个数组，数组表示在第 i 天股票的价格，求最好的方案来买卖股票得到的收益值。
 * 如果股票一路下跌，则收益为0。（也就是说可以初始化 result=0）
 * 题目要求判空，不然 Submit 以后会报越界
 *
 * @Author Antony
 * @Since 2018/7/6 17:39
 */
public class BestTimeToBuyAndSellStock {

    public static void main(String[] args) {
        int[] p1 = new int[]{};
        System.out.println(maxProfit(p1));
    }

    /**
     * leetcode beats 100.0%
     * 时间复杂度：O(N)
     * 最简单的动态规划问题
     * 保存之前的最小价格 和 收益
     * 每次判断是否比最小价更小，如果更小则更新min，大的话判断是否收益会更高。
     */
    public static int maxProfit(int[] prices) {
        // leetcode judge 要求判空, 否则会抛出越界
        if(prices.length <= 1){
            return 0;
        }
        int min = prices[0];
        int result = 0, tmp;
        for(int i=1; i<prices.length; i++){
            if(min > prices[i]){
                min = prices[i];
            }else{
                tmp = prices[i] - min;
                result = tmp > result ? tmp : result;
            }
        }
        return result;
    }


    /**
     * 自己第二次练习
     * 注意min初始值设置为 prices[0]; 然后遍历从1开始
     * @param prices
     * @return
     */
    public static int maxProfit_myTest(int[] prices){
        if(prices.length == 0){
            return 0;
        }
        int profit=0, tmp;
        int min=prices[0];
        for(int i=1; i<prices.length; i++){
            if(prices[i] < min){
                min = prices[i];
            }else{
                tmp = prices[i] - min;
                profit = tmp > profit ? tmp : profit;
            }
        }
        return profit;
    }
}
